package projet.metier;

import java.util.HashMap;

import javax.swing.JOptionPane;

import edu.uci.ics.jung.graph.Graph;

/**
 * Dijkstra's algorithm
 * @author Julien
 */
public class DijkstraAlgorithm {

	//Used to store all the results of the dijkstra's algorithm to avoid unnecessary recalculations
	private static HashMap<Graph<String, Integer>, HashMap<String, HashMap<String, Object[]>>> dijkstraMap = new HashMap<>(); 
	
		
	/**
	 * Dijkstra's algorithm to find shortest path from one vertex to all the others
	 * @param G - Graph<String, Integer> - Graph on which Dijkstra must be calculated
	 * @param s - String - Source vertex.
	 * @return Hashmap<String s, Object[] o> - s: Vertex - o[0]: Distance - o[1]: Predecessor(null for source vertex)
	 */
	public static HashMap<String, Object[]> Dijkstra (Graph<String, Integer> G, String s) {
		
		HashMap<String, Object[]> retour = new HashMap<>();
		
		if (dijkstraMap != null && dijkstraMap.containsKey(G) && dijkstraMap.get(G).containsKey(s)){
			retour = dijkstraMap.get(G).get(s);
		} else {
			try {
				if (G.getVertices().contains(s)){
					Object[] list = G.getVertices().toArray();
					HashMap<String, Integer> hashList = new HashMap<String, Integer>();//Link between list of vertices and other arrays
					int[] dist = new int [G.getVertexCount()];  // shortest known distance from "s"
					String[] pred = new String [G.getVertexCount()];  // preceding node in path
					boolean[] visited = new boolean [G.getVertexCount()]; // all false initially
					
					//Fills hashList with vertices as keys and an int as value
					//This int is used as index in the other arrays 
					for (int i=0; i<list.length;i++){
						hashList.put((String)list[i], i); 
					} 
					
					//Sets every distance to infinity (Integer.MAX_VALUE is as close as we'll get)
					for (int i=0; i<dist.length; i++) {
						dist[i] = Integer.MAX_VALUE;
					}
					dist[hashList.get(s)] = 0;//Sets distance to source vertex to 0
				
					for (int i=0; i<dist.length; i++) {
						final int next = minVertex (dist, visited);
						visited[next] = true;
					
						// The shortest path to next is dist[next] and via pred[next].
						final Object [] n = G.getNeighbors((String)list[next]).toArray();
						for (int j=0; j<n.length; j++) {
							final String v = (String) n[j];
							final int d = dist[next] + 1;
							if (dist[hashList.get(v)] > d) {
								dist[hashList.get(v)] = d;
								pred[hashList.get(v)] = (String) list[next];
							}
						}
					}
					
					for (int i=0; i<list.length;i++){
						Object[] o = new Object[2];
						o[0] = dist[i];
						o[1] = pred[i];
						retour.put((String)list[i], o);
					}
					
					//Adds the results in the static variable for later use
					if (dijkstraMap != null && !dijkstraMap.containsKey(G)){
						dijkstraMap.put(G, new HashMap<String, HashMap<String, Object[]>>());
					}
					dijkstraMap.get(G).put(s, retour);
					
				}
			} catch (Exception e) {
				JOptionPane.showMessageDialog(null, "Une erreur est survenue lors de l'utilisation de l'algorithme de Dijkstra:\n"+e.getMessage(), "Erreur", JOptionPane.ERROR_MESSAGE);
			}
		}

		return  retour;
	}

	/**
	 * Selects the next closest vertex that hasn't been visited yet.
	 * @param dist - int[] - Distance table.
	 * @param v - boolean [] - Boolean table to know whether a vertex has been visited or not.
	 * @return integer - Corresponding to the next vertex to visit.
	 */
	private static int minVertex (int[] dist, boolean [] v) {
		int x = Integer.MAX_VALUE;
		int y = -1;   // graph not connected, or no unvisited vertices
		for (int i=0; i<dist.length; i++) {
			if (!v[i] && dist[i]<x) {y=i; x=dist[i];}
		}
		return y;
	}

}
